In most current communication networks, a large number of nodes are connected through wireless and wired links into a web of interconnections that make up the network topology. Wireless links may be established and torn down quickly and may possess a short life-time; even wired networks are non-stationary and their topology may vary over time since links are constantly being established and terminated. Although changes in the actual hard-wired infrastructure are infrequent, terminals, switches, computers and other forms of network devices or nodes may be connected and disconnected to existing ports or be integrated into a network at any time. Frequently, both intentionally and unintentionally, networks of any size may contain loops and provide for a mesh-like topology rather than a tree-like topology. Loops may be introduced into the network deliberately in order to provide for redundancy in case of link failure, or unintentionally by overlooking that a node is connected to multiple other nodes that may then form a loop. Ad-hoc and other loosely organized types of networks are inherently mesh networks.
However, for current network technology, a mesh-like topology comprising network loops present a problem for various networking protocols, particularly at Layer 2, the data link layer. For example, a variety of networking functions require information to be broadcast throughout a network. This may typically be achieved by so-called flooding, whereby every switch (or node) forwards a packet or frame intended for broadcast, on all the active links, except for the link on which the packet was received. Clearly, if there are loops in the network, the broadcast packets will eventually arrive back at the sender and be re-sent over the active links. This leads to an accumulation of packets in the network and may ultimately lead to the collapse of the network due to an excessively large number of broadcast packets. This phenomenon is also referred to as a broadcast storm.
To avoid these problems, it is necessary for the network to be organized in a tree-like structure, characterized by the property that only one path exists between any two nodes in the network and hence no loops. This may be achieved by overlaying the network with a virtual tree network, electronically disabling the links that would form loops. Such a tree that includes all the nodes in the network and therefore provides a connection between any two nodes is referred to as a spanning tree, as it spans the network. In some networks, sophisticated algorithms are employed to construct a tree topology in a manner to optimize the network performance. Furthermore, these algorithms are typically dynamic in order to be able to reconfigure the network in case of topology changes due to movement of nodes or link failures, for example. Such algorithms naturally introduce significant complexity into a network and require substantial computing power in comparison to a network that is static and constructed as a tree structure from the onset.
Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art, through comparison of such systems with some aspects of the present invention as set forth in the remainder of the present application with reference to the drawings.